1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
Medium

You are given a rectangular cake of size h x w and two arrays of integers horizontalCuts and verticalCuts where:

  • horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, and
  • verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut.

Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a large number, return this modulo 109 + 7.

 

Example 1:

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4 
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green piece of cake has the maximum area.

Example 2:

Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
Output: 6
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green and yellow pieces of cake have the maximum area.

Example 3:

Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
Output: 9

 

Constraints:

  • 2 <= h, w <= 109
  • 1 <= horizontalCuts.length <= min(h - 1, 105)
  • 1 <= verticalCuts.length <= min(w - 1, 105)
  • 1 <= horizontalCuts[i] < h
  • 1 <= verticalCuts[i] < w
  • All the elements in horizontalCuts are distinct.
  • All the elements in verticalCuts are distinct.
Accepted
63K
Submissions
171.5K
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
Sort the arrays, then compute the maximum difference between two consecutive elements for horizontal cuts and vertical cuts.
Show Hint 2
The answer is the product of these maximum values in horizontal cuts and vertical cuts.

Average Rating: 5.00 (17 votes)

Premium

Solution


Overview

Calculating the area of every possible piece of cake can get out of hand very quickly. In the first example alone, there are already 12 pieces of cake, and our input can have up to 100,000 vertical and horizontal cuts. We need a smarter way to find the area of the largest piece of cake.

The key insight to solve this problem is that not all of the pairs of horizontal and vertical cuts matter. Let's take a step back - the area of a cake piece is defined by width * height. If we were to consider only the horizontal cuts, then we would end up with many pieces of cake with width = w and varying heights. For each new piece, making a vertical cut will change the width, but not the height.

Let's use the first test case in the problem description as an example. If we were to only apply the horizontal cuts [1, 2, 4], we will end up with 4 pieces of cake, all with width = 4. Take the piece of cake with height = 2 between the cuts at 2 and 4, and make any vertical cut you want - notice that the height will always be 2. The same logic can be applied when considering the vertical cuts first - we will have many pieces of cake with height = h and varying widths.

Therefore, we know the largest piece of cake must have a height equal to the tallest height after applying only the horizontal cuts, and it will have a width equal to the widest width after applying only the vertical cuts.

Current
1 / 3


Approach: Sort

Intuition

As mentioned above, we can find the max height and the max width separately. Our final answer will be maxHeight * maxWidth. Each height and width is defined by the distance between 2 cuts. In the first example, the max height of 2 is defined by the distance between cuts 2 and 4 (4 - 2 = 2). To find all heights and widths, we must first sort our inputs horizontalCuts and verticalCuts. This will ensure that all of the cuts that are beside each other on the cake are also beside each other in the array. Then, we can iterate through the sorted inputs one at a time and find each height or width by simply taking the difference between two adjacent cuts.

One thing to be careful about is the edges. For cuts in the middle, the distance is defined by the difference between two cuts. However, for the edges, they are defined by the cake's dimensions.

  • The top-most cut's height will be equal to horizontalCuts[0], while the bottom-most cut's height will be equal to h - horizontalCuts[horizontalCuts.length - 1].
  • The left-most cut's width will be equal to verticalCuts[0], while the right-most cut's width will be equal to w - verticalCuts[verticalCuts.length - 1].

Algorithm

  1. Sort both horizontalCuts and verticalCuts in ascending order.

  2. Initialize a variable maxHeight as the larger of the top and bottom edge: maxHeight = max(horizontalCuts[0], h - horizontalCuts[horizontalCuts.length - 1]).

  3. Iterate through horizontalCuts starting from index 1 (skip the 0th index since it represents the edge cut, which we accounted for in the previous step). At each iteration, find the height defined by the ithi^{th} cut and the nearest cut above, horizontalCuts[i] - horizontalCuts[i - 1]. Update maxHeight if necessary.

  4. Initialize a variable maxWidth as the larger of the left and right edge: maxWidth = max(verticalCuts[0], w - verticalCuts[verticalCuts.length - 1]).

  5. Iterate through verticalCuts starting from index 1. At each iteration, find the width defined by the ithi^{th} cut and the nearest cut to the left, verticalCuts[i] - verticalCuts[i - 1]. Update maxWidth if necessary.

  6. Our maximum area is maxHeight * maxWidth. Don't forget the modulo 109+710^{9} + 7, and depending on what language you're using, be careful of overflow. Return the maximum area.

Implementation

Complexity Analysis

Given NN as the length of horizontalCuts and MM as the length of verticalCuts,

  • Time complexity: O(Nlog(N)+Mlog(M))O(N \cdot \log(N) + M \cdot \log(M))

    Sorting an array of length nn costs nlognn \cdot logn time. We need to sort both horizontalCuts and verticalCuts, which is why both are present in the time complexity. Although we also iterate through both arrays, which costs O(N)O(N) and O(M)O(M) time, these iterations are not as expensive as the sorting, and by the rules of Big O, do not get included in the final time complexity.

  • Space complexity: O(1)O(1)

    Regardless of the input size, we only ever need to use 2 variables: maxHeight and maxWidth.



Report Article Issue

Comments: 10
pejato's avatar
Read More

It is possible to do this in O(n) actually. This problem is essentially the same as https://leetcode.com/problems/maximum-gap/ which has an O(n) bucket sort solution.

Runtime fluctuates a lot but this solution beats 100% time (28ms) using the maximum gap solution as a subroutine.

int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
    auto [maxHGap, minHCut, maxHCut] = maxGapAndExtrema(horizontalCuts);
    auto [maxVGap, minVCut, maxVCut] = maxGapAndExtrema(verticalCuts);
    
    int maxH, maxV;
    
    if (maxHGap != -1)
        maxH = max({minHCut, h - maxHCut, maxHGap});
    else
        maxH = max(horizontalCuts.front(), h - horizontalCuts.back());
    
    if (maxVGap != -1)
        maxV = max({minVCut, w - maxVCut, maxVGap});
    else
        maxV = max(verticalCuts.front(), w - verticalCuts.back());

    const int m = 1000000007;

    return (static_cast<long>((maxH%m)) * (maxV%m) %m);
}

tuple<int, int, int> maxGapAndExtrema(vector<int>& nums) {
    // Sentinel
    if (nums.size() <= 1)
        return {-1, -1, -1};
    
    int minVal = INT_MAX, maxVal = INT_MIN;
    
    for (int num : nums) {
        minVal = min(minVal, num);
        maxVal = max(maxVal, num);
    }
    
    assert(minVal != maxVal);
    
    const int size = nums.size()-1;
    const int smallestPossibleGap = static_cast<int>(
        ceil(static_cast<double>(maxVal - minVal) / size)
    );

    int* __restrict__ minBuckets = new int[size];
    fill(minBuckets, minBuckets+size, INT_MAX);
    
    int* __restrict__ maxBuckets = new int[size];
    fill(maxBuckets, maxBuckets+size, INT_MIN);
    
    for (int num : nums) {
        if (num == minVal || num == maxVal)
            continue;
        int idx = (num - minVal) / smallestPossibleGap;

        minBuckets[idx] = min(minBuckets[idx], num);
        maxBuckets[idx] = max(maxBuckets[idx], num);
    }

    int maxGap = INT_MIN;
    int prev = minVal;
    
    for (int i=0; i<nums.size()-1; ++i) {
        if (minBuckets[i] == INT_MAX && maxBuckets[i] == INT_MIN)
            continue;
        maxGap = max(maxGap, minBuckets[i] - prev);
        prev = maxBuckets[i];
    }
    
    delete[] minBuckets;
    delete[] maxBuckets;
    return { max(maxGap, maxVal - prev), minVal, maxVal };
}

11
Reply
Share
Report
bplacker's avatar
Read More

Pretty well written article. This is a good lesson in clarifying requirements during an interview (needing to sort the arrays).

7
Show 1 reply
Reply
Share
Report
Yedelm's avatar
Read More

A dangerous mistake I made is missed the boundary of those numbers and used int instead of long for the max value.. post here to remind myself

3
Reply
Share
Report
nandanphadke's avatar
Read More

Shouldn't this be a Easy? Maybe I am missing something, but what makes this problem a Medium?

1
Reply
Share
Report
xsm90827's avatar
Read More

FYI, long is 8 bits size and int is 4 bits size, so if I use int for the maxHeight and maxWidth, it will be an overflow and truncated

0
Show 1 reply
Reply
Share
Report
florin5's avatar
Read More

The operation on the cuts (vertical or horizontal) is the same: find the biggest cut, so the code can be refactored to reuse/reduce number of lines of code :

class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        result = [0,0]
        for idx, items in enumerate([(horizontalCuts,h),(verticalCuts,w)]):
            cuts,max_cut = items
            cuts.append(0)
            cuts.append(max_cut)
            cuts.sort()
            for i in range(len(cuts)-1):
                result[idx] = max(result[idx], cuts[i+1]-cuts[i])
        return result[0]*result[1] %(10**9 + 7)

Further more he code can be simplified by extracting the max_cut computation in a stand alone function.

0
Reply
Share
Report
lesliehk's avatar
Read More

There are magical lines in the >99.5% solution in Python. May I ask if anyone knows why?

if h == 1000000000:
            return 755332975

0
Show 1 reply
Reply
Share
Report
shashi85's avatar
Read More

Why maxDiff is not calculated with leftMost or upperMost condition? i.e. maxHeight = Math.max(maxHeight, horizontalCuts[i] - 0); and maxWidth = Math.max(maxWidth, verticalCuts[i] - 0);

0
Show 1 reply
Reply
Share
Report
codingpreparation's avatar
Read More

Cannot understand why this fails the final test case . The maxColumn and MaxRow are correctly returned yet the final modulo calculation does not return the result

    Arrays.sort(horizontalCuts);
    Arrays.sort(verticalCuts);
    int[] modifiedHorizontalCuts = new int[horizontalCuts.length+2];
    int[] modifiedVerticalCuts = new int[verticalCuts.length+2];
    for(int i = 0;i<modifiedHorizontalCuts.length;i++){
        if(i==0) {
            modifiedHorizontalCuts[i] = 0;
            continue;
        }
        if(i==modifiedHorizontalCuts.length-1) {
            modifiedHorizontalCuts[i] = h;
            continue;
        }
        modifiedHorizontalCuts[i] = horizontalCuts[i-1];
    }
    
    for(int i = 0;i<modifiedVerticalCuts.length;i++){
        if(i==0) {
            modifiedVerticalCuts[i] = 0;
            continue;
        }
        if(i==modifiedVerticalCuts.length-1) {
            modifiedVerticalCuts[i] = w;
            continue;
        }
        modifiedVerticalCuts[i] = verticalCuts[i-1];
    }
    
    int maxRow = 0;
    for(int i=1;i<modifiedHorizontalCuts.length;i++){
        maxRow = Math.max(maxRow,modifiedHorizontalCuts[i]-modifiedHorizontalCuts[i-1]);
    }
    
    int maxColumn = 0;
    for(int i=1;i<modifiedVerticalCuts.length;i++){
        maxColumn = Math.max(maxColumn,modifiedVerticalCuts[i]-modifiedVerticalCuts[i-1]);
    }
    // if(h==1000000000)
    //     System.out.println("Max Column "+maxColumn+" Max Row"+maxRow);
    //return (int)  ( ( maxColumn * maxRow ) % (1e9 + 7) );
    return (int) ((maxColumn * maxRow) % (1e9 + 7));`

0
Show 2 replies
Reply
Share
Report
Randy_Marsh's avatar
Read More

Why does this fail for the final Testcase? Can anyone please suggest?

class Solution {
    public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        Arrays.sort(horizontalCuts);
        Arrays.sort(verticalCuts);
        
        int largestHorizontal = getLargestPiece(horizontalCuts, h);
        int largestVertical = getLargestPiece(verticalCuts, w);
        
        return (int) ((largestHorizontal * largestVertical) % 1000000007);
    }
    
    private int getLargestPiece(int[] cuts, int total){
        int prevCut = 0;
        int largestPiece = 0;
        
        for(int cut : cuts){
            int currentPiece = cut - prevCut;
            largestPiece = Math.max(largestPiece, currentPiece);
            prevCut = cut;
        }
        largestPiece = Math.max(largestPiece, total - prevCut);
        
        return largestPiece;
    } 
}

0
Show 3 replies
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
06/03/2021 12:55Accepted84 ms32.1 MBcpp
05/31/2020 08:24Accepted356 ms32.2 MBcpp
05/31/2020 08:15Runtime ErrorN/AN/Acpp
05/31/2020 08:14Runtime ErrorN/AN/Acpp
/23
Contribute
|||
Saved
Trie
This list is empty.